package com.gjx.leetcode;
//79. 单词搜索
//给定一个二维网格和一个单词，找出该单词是否存在于网格中。
//
//单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
//
//示例:
//
//board =
//[
//  ['A','B','C','E'],
//  ['S','F','C','S'],
//  ['A','D','E','E']
//]
//
//给定 word = "ABCCED", 返回 true.
//给定 word = "SEE", 返回 true.
//给定 word = "ABCB", 返回 false.


public class Solution079 {
	public boolean exist(char[][] board, String word) {
        
		char[] c = word.toCharArray();
		boolean[][] mark = new boolean[board.length][board[0].length];
		
		for (int i=0; i<board.length; i++) {
			for (int j=0; j<board[0].length; j++) {
				if (dfs(board, i, j, c, 0, mark)) {
					return true;
				}
			}
		}
		return false;
    }
	
	
	private boolean dfs(char[][] board, int x, int y, char[] word, int start, boolean[][] mark) {
		
		if (start > word.length) {
			return false;
		} else if (start == word.length) {
			return true;
		}
		
		if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
			return false;
		}
		
		if (mark[x][y]) {
			return false;
		}
		
		if (board[x][y] != word[start]) {
			return false;
		}
		
			
		mark[x][y] = true;
		if (dfs(board, x-1, y, word, start+1, mark)) {
			return true;
		}
		if (dfs(board, x+1, y, word, start+1, mark)) {
			return true;
		}
		if (dfs(board, x, y-1, word, start+1, mark)) {
			return true;
		}
		if (dfs(board, x, y+1, word, start+1, mark)) {
			return true;
		}
		mark[x][y] = false;
			
		return false;
		
	}
	
	public static void main(String[] args) {
		new Solution079().exist(new char[][]{{'a'}}, "a");
	}
}
